1. Field of the Invention
This invention generally relates to real-time, knowledge-based control of both small-scale systems and large-scale systems. More particularly, this invention relates to computer-based control of systems distributed in space and/or time that are composed of components whose logical (set-based) and evolution (continuum-based) behaviors are controlled by a collection of agents.
2. Discussion of the Related Technology
Computer-controlled systems are collections of components used either to advise humans in executing their control responsibilities or to autonomously execute appropriate control actions. Computer-controlled systems may also have a combination of both advisory components and autonomous components.
Typical components of distributed, real-time computer-controlled systems include computers, communication networks, software, sensors (analog-to-digital transducers), and actuators (digital-to-analog transducers). Systems are controlled to achieve and maintain desired high-level event-based goals (such as safety goals or quality goals) often expressed by rules of desired behavior and are controlled to achieve desired low-level evolution-based goals (such as accurate rate of change of angular position or precision control of displacement velocity) often expressed as differential or difference equations.
Current engineering environments provide support for conducting extensive experiments for trying out various control mechanisms. Major efforts have been conducted over the past few decades to provide ever more precise statements of system constraints and ever more powerful simulation environments for conducting more extensive combinations of experiments to discover failure modes of the contemplated control mechanisms. As systems are being analyzed, designed, implemented, and maintained, these extensive experiments conducted in the engineering environment are used to perform verification, validation, and accreditation of the models and algorithms used by the computer-controlled system to achieve autonomous or semi-autonomous (human-in-the-loop) control of the distributed system.
The existing technical approach has met with great success for small-scale systems. However, according to the U.S. Department of Commerce, as many as seventy to ninety percent of real-time systems fail to ever meet their goals and be deployed. Moreover, for those systems that are deployed, the fraction of initial system cost attributable to software continues to rise, accounting for between thirty to ninety percent of initial acquisition costs. A primary cause of failure in constructing large-scale, distributed systems is the difficulty of synchronizing real-time processes.
The best existing technology relies on engineering experience and heuristics to build computer-controlled systems that combine logical constraints, geometric constraints, and evolution constraints on system behavior. Verification, validation, and accreditation of these systems is achieved through expensive and inconclusive development efforts that attempt to discover and correct system failure modes through a series of simulation or benchmark experiments followed by correction of discovered failure modes. As indicated above, large-scale, real-time control efforts often fail and the projects are abandoned after expenditure of significant resources. Those that are successful are difficult to update, because the series of verification, validation, and accreditation experiments must be repeated whenever the system is changed.
The invention improves over the current technology through the generation of control software that meets declared constraints. The technology is based on rigorous mathematical results that establish that the approach is sound (will not prove a theorem that contradicts assertions in the knowledge base) and complete (will prove theorems that generate actions to cause the system state to reach (within declared closeness criteria) any point that is in the range of points described by the knowledge base). This formal theoretical result, and the practical implementation of the result in the invention, enables the incremental construction of large-scale, distributed, real-time control systems from trusted components. Thus, to the extent that an existing component has achieved a degree of trust, the invention enables inclusion of that component in a larger system, without repeating the previous experiments. Moreover, for smaller well-understood systems constructed from legacy, product-line applications, the invention enables reliable implementation of a wider variability in system parameters.
There are no products similar to the Multiple-Agent Hybrid Control Architecture (MAHCA). Features of MAHCA include:
1. MAHCA uses general descriptions of system state that combine logical and evolution constraints on system behavior. The best commercial simulation products have supported such combined descriptions of system behavior for many years. Examples of commercial simulation systems include SIMNON and ACSL, both of which support nonlinear system descriptions, discovery of system equilibrium points, and linearization about system equilibria for design of linear controllers. The best experimental prototype is DSTOOL from Cornell University, which uses a system description closest to that of MAHCA. A recent Ph.D. thesis by Mats Anderson from Lund Institute of Technology discusses simulation of hybrid systems. The thesis describes the systems modeling language Omola and the simulation system OmSim. While these products and experimental systems support discovery of system behavior, including discovery of failure modes, they do not support creation of controllers to compensate for undesired behaviors. PA0 2. MAHCA's logical and evolution description of system behavior delivers cumulative control solutions. Commercial products for design of control systems exist, including some that generate control code from experiments. The best commercial systems are MATLAB, MATRIX-X, and BEACON. The best experimental prototypes are ANDECS from Germany, HONEY-X from Honeywell, and METL from University of Waterloo. METL is closest in spirit to MAHCA in that METL supports both logical and evolution descriptions of system behavior and delivery of control solutions that meet logical and evolution constraints. METL, however, relies on experimental discovery of failure modes and application of engineering heuristics to construct combined solutions, as do all other control design tools currently available. PA0 3. MAHCA supports a system for solving both linear and nonlinear scheduling of events. Commercial products exist for scheduling discrete sequences of events. An extension to the G2 product from Gensym Corp. is currently being marketed as an optimal scheduling package for discrete manufacturing. This product, like other scheduling packages, relies on solution of a linear approximation to what is known to be a nonlinear problem. MAHCA solves the nonlinear scheduling problem as well as its linear approximation. PA0 4. MAHCA uses a general purpose architecture descriptor. General purpose architectures for large-scale, real-time systems have been under development for some time. The NASREM architecture, a joint development of the National Bureau of Standards and the National Aeronautics and Space Administration, was published as an open standard in 1989. This reference architecture for real-time, distributed control has been used as a starting point for several large-scale systems as well as the beginning of the Next Generation Controller project and the beginning of two projects in component-based programming supported by the Advanced Research Projects Agency (ARPA) Domain-Specific Software Architecture (DSSA) project. One of these projects has the best experimental prototype for declaring system architectures, the ARDEC-TEKNOWLEDGE (ARTEK) model. Neither NASREM nor ARTEK, however, support development of control programs for the systems described by their architectural syntax. MAHCA can use either NASREM or ARTEK syntax to describe reference architectures for large-scale systems and can also can generate control software to execute actions necessary to meet the design goals of the architecture applications. Also, while both NASREM and ARTEC support declarations of synchronization requirements for large-scale distributed system, neither support construction of control solutions that achieve the required synchronization. PA0 1. NASREM supports separation of complex real-time systems into a fixed hierarchy based upon lower levels of the hierarchy being implemented at faster time scales and higher levels in the hierarchy being implemented at slower time scales. The time scales nominally vary from several hours of observations of system evolution at the slowest time scale to several milliseconds of observations of system evolution at the fastest time scale. PA0 2. NASREM supports a further separation of complex, real-time systems into fixed heterarchical partitions at each layer in the hierarchy which correspond to components for a fixed, closed-loop approach for control of each layer according to a sense-decide-act paradigm of: PA0 3. NASREM separates system behaviors into major logical activities being conducted based upon nominal partitioning according to system time scales. This supports a deliberate design of adding higher-level logical functionality in layers from the simplest to the most elaborate as the complex system is incrementally designed, prototyped, assembled, tested, and commissioned. PA0 1. Reformulate the original problem as a calculus of variations problem on a carrier manifold of system states. The carrier manifold is the combined simulation model of the network and the simulation models at the nodes. State trajectories and their evolution occurs on this carrier manifold. This method seeks control functions of the state of the system for the global and local problems that minimize a non-negative cost function on state trajectories whose minimization perfectly achieves all the required goals of the distributed real-time control problem. PA0 2. Replace the standard calculus of variations problem with a convex variational problem by convexifying, with respect to the state rate u, the Lagrangian L(x, u) that represents the cost function being minimized. The convexified problem has a solution that is a measure-valued (sometimes referred to as weak or L. C. Young) solution to the original problem. This solution is a chattering control that chatters appropriately between local minima of the original problem so as to achieve close to the global minimum of the original problem. This solution, however, is only abstract and gives local and global control functions of time. PA0 3. To get feedback control functions of state instead, convert the convexified variational problem to an appropriate Hamilton-Jacobi-Bellman equation form. This transformation is done by the planner of the MAHCA agent automatically. An ".epsilon.-solution" of this equation for the appropriate boundary conditions gives valid infinitesimal transformations on the state space representing the generators of feedback controls. PA0 4. The control functions that are possible at a given state are a cone in the tangent space, and move with the tangent space. Following the optimal state trajectory produces the near-optimal corresponding controls. The controls are algebraically dependent on the Christoffel symbols of an affine connection that is characteristic of the Carrier manifold. The affine connection gives the real-time state transition function of the global and local automata, or control programs, needed to govern the communications network and the approximations at nodes in order to meet the prescribed goal. The global program takes responsibility for message passing between nodes; the local programs take responsibility for local updates in real time. Required dynamics of the global system are achieved without central control (global umpire) of the distributed system by enforcing continuity conditions at each node. PA0 1. MAHCA supports separation of complex real-time systems into a nominal hierarchy based upon lower levels of the hierarchy being implemented at faster time scales and higher levels in the hierarchy being implemented at slower time scales and also supports on-line creation of automata that react at intermediate time scales so that, in effect, a continuum hierarchy is supported. The time scales nominally vary from several hours of observations of system evolution at the slowest time scale to several milliseconds of observations of system evolution at the fastest time scale. Moreover, MAHCA can be configured to react to create links between layers in the nominal hierarchy so that timing constraints for rare events can be met at the time they occur. PA0 2. MAHCA supports a further separation of complex, real-time systems into fixed heterarchical partitions at each layer in the hierarchy that correspond to components for a fixed, closed-loop approach for control of each layer according to a sense-decide-act paradigm similar to the NASREM sequence. Each heterarchical partition proceeds at a fixed rate to implement the sense-decide-act cycle for the level it controls. However, MAHCA also supports on-line creation of automata that react at intermediate time scales so that, in effect, a continuum heterarchy is supported. For example, a normal engineering activity is to separate complex processes into intermediate steps and arrange the sequence of steps into a scenario of activities that are then executed with or without human intervention. PA0 3. MAHCA supports the separation of system behaviors into major logical activities conducted based upon nominal partitioning according to system time scales. This supports a deliberate design of adding higher-level logical functionality in layers from the simplest to the most elaborate as the complex system is incrementally designed, prototyped, assembled, tested, and commissioned. Thus, it is possible to configure MAHCA to be a more flexible implementation of a experimentation-based architecture. However, MAHCA also supports a more general assemblage of components based upon defining behaviors of agents which can then be modified on-line in accordance with pre-arranged relaxation criteria.
MAHCA provides technology for flexible implementations of heterogeneous systems which substantially expand on the capabilities of real-time control architectures envisioned by the National Institute of Standards and Technology (NIST) and the National Aeronautics and Space Administration (NASA) in "NASA/NBS Standard Reference Model for Telerobot Control System Architecture (NASREM)," NIST (formerly NBS) Technical Note 1235, April 1989. The NASREM experimentation-based architecture represents the most logical arrangement of tools for experimental development of intelligent, real-time, computer-controlled systems. The NASREM architecture has been one of the most widely implemented architectures for large-scale systems and was the starting point for real-time, component-based control research being conducted by the Department of Defense. NASREM has several very useful features which are implemented in the MAHCA agents, including:
a. Sense the state of the system at each layer (time scale) in the hierarchy. Analog-to-digital transducers are used to automatically sense and provide inputs at the lowest levels in the hierarchy while user interfaces are used to obtain human queries, response to system queries, or decisions at the highest layers in the hierarchy. PA1 b. Decide which action or plan should be implemented. Scheduling algorithms for sequential machines used for a discrete-event system, switching tables experimentally produced for accomplishing gain-scheduling for closed-loop control algorithms appropriate for different operating modes, or adaptive control algorithms appropriate for use around well-defined operating points are used to decide what actions are to be taken at the lowest layers in the hierarchy. PA1 c. Act to execute the appropriate action for the current state of the system at each layer in the hierarchy. Since lower levels operate at faster time scales than higher levels in the hierarchy (the lowest level being several orders of magnitude faster than the highest level), many actions are taken at a lower level for each action taken at a higher level.
Each hierarchical partition proceeds at a fixed rate to implement the sense-decide-act cycle for the level it controls. The rate can be designed into the system based upon the performance requirements of the users, or the rate may be experimentally determined based upon the physical requirements of existing processes. Each layer accesses a global knowledge base that contains the knowledge of the current state of the system and constraints concerning decisions that can be made for the next cycle.
NASREM, and other architectures based upon conducting extensive experiments to implement complex, large-scale systems, has been a successful engineering approach. However, as systems grow in size and complexity, this technology has been increasingly less effective in achieving successful implementations. A central problem of all these architectures is that the synchronization of levels is application dependent. In MAHCA synchronization is done with a generic invariance principle. Another serious drawback is that the construction of the levels is not provably correct by effective methods.